package com.xiayuanxing.arithmetic.DataStructures.Sort;

import java.util.Arrays;

/**
 * @program: arithmetic
 * @description: 冒泡排序
 * @author: xia yuan xing
 * @create: 2021-09-23 17:18
 */
public class BubbleSort {

    public static void main(String[] args) {
        int arr[] = {3,9,-1,10,-2,100,-99,22,35,1};

        //冒泡排序的演变过程
        //1.第一趟排序就是将最大的数排在最后
        //临时变量
        int temp = 0;
        for (int i = 0; i <arr.length - 1 ; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr[i] > arr[i + 1]){
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        System.out.println("第一趟排序后的数组"+ Arrays.toString(arr));

        //第二趟排序，将第二大数排在倒数第二位
        for (int i = 0; i <arr.length - 1 -1 ; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr[i] > arr[i + 1]){
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        System.out.println("第二趟排序后的数组"+ Arrays.toString(arr));

        //第三趟排序，将第三大数排在倒数第三位
        for (int i = 0; i <arr.length - 1 -2 ; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr[i] > arr[i + 1]){
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        System.out.println("第三趟排序后的数组"+ Arrays.toString(arr));

        //第四趟排序，将第四大数排在倒数第四位
        for (int i = 0; i <arr.length - 1 -3 ; i++) {
            //如果前面的数比后面的数大，则交换
            if (arr[i] > arr[i + 1]){
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        System.out.println("第四趟排序后的数组"+ Arrays.toString(arr));



        //最终排序算法
        bubbleSort(arr);
    }


    /**
     * 冒泡排序  时间复杂度 O(n^2)
     * @param array
     */
    public static void bubbleSort(int[] array){
        //临时变量
        int t = 0;
        //标识变量，表示是否进行过交换
        boolean flag = false;
        for (int i = 0; i <array.length-1 ; i++) {
            for (int j = 0; j <array.length-1 -i ; j++) {
                if (array[j] > array[j+1]){
                    flag = true;
                    t = array[j];
                    array[j] = array[j+1];
                    array[j+1] = t;
                }
            }

            if (!flag){
                //表示在排序中一次都没有交换过
                break;
            }else {
                //重置flag
                flag = false;
            }
        }
        System.out.println("排序后的"+Arrays.toString(array));



    }
}